﻿
namespace Leetcode.N0877;
public class Solution
{
    public bool StoneGame(int[] piles)
    {
        var ans = new (int sum, int index)[piles.Length][];
        for (int i = 0; i < piles.Length; i++)
        {
            ans[i] = new (int sum, int index)[piles.Length];

            for (int j = 0; j < piles.Length - i; j++)
            {
                if (i == 0)
                {
                    ans[i][j] = (piles[j], j);
                }
                else
                {
                    int start = j;
                    int end = j + i;

                    var nextSelectStart = ans[i - 1][start + 1];
                    var selectStartSum = piles[start] + nextSelectStart.sum;

                    var nextSelectEnd = ans[i - 1][start];
                    var selectEndSum = piles[end] + nextSelectEnd.sum;

                    if (selectStartSum >= selectEndSum)
                    {
                        ans[i][j] = (selectStartSum, start);
                    }
                    else
                    {
                        ans[i][j] = (selectEndSum, end);
                    }
                }
            }
        }

        var sum = piles.Sum(i => i);
        var aliceSum = ans[ans.Length - 1][0].sum;
        return aliceSum > sum - aliceSum;
    }
}